/*
	KMP算法
*/

#include <stdio.h>
#include <string.h>
int *getNext(char P[])
{
	int tempK = -1;
	int i = 0;
	int length = strlen(P);
	int *next = new int[length];
	next[0] = -1;  //首位为0
	while (i < length - 1)
	{
		while (tempK >= 0 && P[i] == P[tempK])  //利用之前的特征值
			tempK = next[tempK];
		i++;  //位置后滑
		tempK++;  //特征值加一
		if (P[i] == P[tempK])  //优化
			next[i] = next[tempK];
		else  //不需优化
			next[i] = tempK;
	}
	return next;
}
int strMatchingWithKMP(int next[], char T[], char P[])
{
	int lengthP = strlen(P);
	int lengthT = strlen(T);
	int i = 0;  //P的下标
	int j = 0;  //T的下标
	if (lengthP > lengthT)
		return -1;
	while (i < lengthP&&j < lengthT)
	{
		if (i == -1 || P[i] == T[j])
			i++, j++;
		else
			i = next[i];
	}
	if (i >= lengthP)
		return j - lengthP + 1;
	return -1;
}
int main(void)
{
	char T[] = "abcdefghijklmn";
	char P[] = "fghij";
	printf("%d",strMatchingWithKMP(getNext(P), T, P));
	return 0;
}
